package offer

/*
时间复杂度:O(N*target)
空间复杂度:O(target)

完全背包问题,每一个物体可以取无限次,则dp[i] = Max(dp[i], dp[i-v]+w)
TODO:
*/

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for _, v := range nums {
		for i := v; i <= target; i++ {
			dp[i] += dp[i-v]
		}
	}
	return dp[target]
}